package com.cb2.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/split-a-circular-linked-list'>拆分循环链表(Split a Circular Linked List)</a>
 * <p>现给定一个由正整数组成的 循环链表 list ，你的任务是将其拆分为 2 个 循环链表 ，使得第一个链表包含 list 前半部分 的节点（即 ceil(list.length / 2) 个节点），顺序与 list 中的顺序相同，而第二个链表包含 list 中 剩余 的节点，顺序也与 list 中的顺序相同。</p>
 * <p>返回一个长度为 2 的数组，其中第一个元素是表示 前半部分 链表的 循环链表 ，第二个元素是表示 后半部分 链表的 循环链表 。</p>
 * <p>循环链表 是一个普通的链表，唯一的区别是最后一个节点的下一个节点是头节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [1,5,7]
 *      输出：[[1,5],[7]]
 *      解释：初始链表有3个节点，因此前半部分是前两个元素，剩下的 1 个节点在后半部分。
 *
 *  示例 2：
 *      输入：nums = [2,6,1,5]
 *      输出：[[2,6],[1,5]]
 *      解释：初始链表有4个节点，因此前半部分是前两个元素，剩下的 2 个节点在后半部分。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>list 中的节点数范围为 [2, 10^5]</li>
 *     <li>0 <= Node.val <= 10^9</li>
 *     <li>LastNode.next = FirstNode ，其中 LastNode 是链表的最后一个节点，FirstNode 是第一个节点。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/14 9:52
 */
public class LC2674SplitCircularLinkedList_M {
    static class Solution {
        public ListNode[] splitCircularLinkedList(ListNode list) {
            ListNode slow = list;
            ListNode fast = list;
            while (fast.next != list && fast.next.next != list) {
                slow = slow.next;
                fast = fast.next.next;
            }
            if (fast.next != list) {
                fast = fast.next;
            }
            ListNode list2 = slow.next;
            slow.next = list;
            fast.next = list2;
            return new ListNode[]{list, list2};
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(5);
        head1.next.next = new ListNode(7);
        head1.next.next.next = head1;

        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(6);
        head2.next.next = new ListNode(1);
        head2.next.next.next = new ListNode(5);
        head2.next.next.next.next = head2;

        Solution solution = new Solution();
        for (ListNode listNode : solution.splitCircularLinkedList(head1)) {
            Set<ListNode> visited = new HashSet<>();
            while (visited.add(listNode)) {
                System.out.print(listNode.val + "   ");
                listNode = listNode.next;
            }
            System.out.println();
        }
        System.out.println("===========");
        for (ListNode listNode : solution.splitCircularLinkedList(head2)) {
            Set<ListNode> visited = new HashSet<>();
            while (visited.add(listNode)) {
                System.out.print(listNode.val + "   ");
                listNode = listNode.next;
            }
            System.out.println();
        }
    }
}
